/**
 * 滑动窗口，也是双指针啦
 * 209.长度最小的子数组(连续子数组)
 * 904.水果成篮
 * 76.最小覆盖子串
 * **/

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution
{
public:
    //209.
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int left = 0, right = 0;
        int n = nums.size();
        int sum = 0; // 窗口和
        int minLen = n + 1;
        while (right < n) {
            sum += nums[right];
            // cout << "sum = " << sum << endl;
            while (sum >= target) {
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                // cout << "sum = " << sum << endl;
                ++left;
            }
            ++right;
        }
        // 窗口和一直小于target，返回0
        return minLen == n + 1 ? 0 : minLen;
    }
    // 904.
    int totalFruit(vector<int> &fruits)
    {
        //{水果类型：水果个数}
        unordered_map<int, int> map;
        int left = 0;
        int maxSize = 0;
        for (int right = 0; right < fruits.size(); ++right) {
            map[fruits[right]] += 1;
            cout << map[fruits[right]] << endl;
            while (map.size() > 2) {
                map[fruits[left]] -= 1;
                if (map[fruits[left]] == 0) {
                    map.erase(fruits[left]);
                }
                ++left;
            }
            maxSize = max(maxSize, right - left + 1);
        }
        return maxSize;
    }
    //76. 返回s覆盖t的最小子串
    string minWindow(string s, string t)
    {
        unordered_map<int, int> tMap;   // t{字符：次数}
        unordered_map<int, int> winMap; // 窗口{字符：次数}
        int i = 0;
        int match = 0; // 记录匹配字符个数
        string sub;
        for (char &ch : t) {
            tMap[ch] += 1;
        }
        for (int j = 0; j < s.length(); ++j) {
            auto it = tMap.find(s[j]);
            if (it != tMap.end()) { // winMap只计算窗口内含t的字符
                winMap[s[j]] += 1;
                // winMap和tMap等时才算匹配
                if (winMap[s[j]] == tMap[s[j]]) {
                    ++match;
                }
            }
            // 已匹配时 tMap和winMap 完全相同
            while (match == tMap.size()) {
                // 寻找最小子串
                if (j - i + 1 < sub.length() || sub.empty()) {
                    sub = s.substr(i, j - i + 1);
                }
                // 对窗口左端点动手
                auto it = winMap.find(s[i]);
                if (it != winMap.end()) {
                    winMap[s[i]] -= 1;
                    if (winMap[s[i]] < tMap[s[i]]) {
                        --match;
                    }
                    if (winMap[s[i]] == 0) {
                        winMap.erase(s[i]);
                    }
                }
                ++i;
            }
        }
        return sub;
    }
};

Solution solve = Solution();

void test209()
{
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    cout << solve.minSubArrayLen(target, nums) << endl;
}

void test904()
{
    vector<int> fruits = {3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};
    cout << solve.totalFruit(fruits) << endl;
}

void test76()
{
    string s = "ADOBECODEBANC", t = "ABC";
    // string s = "a", t = "aa";
    cout << solve.minWindow(s, t) << endl;
}

int main()
{
    // test209();
    // test904();
    test76();

    return 0;
}